package leetcode.p21;

import javax.lang.model.type.MirroredTypeException;
import java.util.*;

/**
 * 合并两个有序的链表
 * 递归
 */
public class Solution {

    //迭代法
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while (list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next  = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 != null) {
            cur.next = list1;
        }
        if(list2 != null){
            cur.next = list2 ;
        }
        return head.next;
    }

//递归法
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    //二叉树镜像
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        swap(root);
        Mirror(root.left);
        Mirror(root.right);
    }

    private void swap(TreeNode root) {
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
    }



    // 对称二叉树
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null)
            return true;
        return  isSymmetrical(pRoot.left,pRoot.right);
    }

    boolean isSymmetrical(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null)
            return true;
        if(t1 == null || t2 == null)
            return false;
        if(t1.val != t2.val)
            return false;
        return isSymmetrical(t1.left,t2.right) && isSymmetrical(t1.right,t2.left);
    }

    //二叉树层序遍历 java
    public void PrintFromTopToBottom(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode nowNode = q.peek();
            q.poll();
            System.out.println(nowNode.val);//打印节点值
            if(nowNode.left!= null){
                q.add(nowNode.left);
            }
            if(nowNode.right != null){
                q.add(nowNode.right);
            }
        }
    }


    // 之子打印二叉树
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        boolean reverse= false;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        while (!q.isEmpty()) {
            int size = q.size();
            ArrayList<Integer> list = new ArrayList<>();
            while (size-- > 0) {

                TreeNode t = q.poll();
                if (t == null) {
                    continue;
                }
                list.add(t.val);
                q.add(t.left);
                q.add(t.right);
            }
            if(reverse){
                Collections.reverse(list);
            }
            if(!list.isEmpty()){
                ret.add(list);
            }
            reverse = !reverse;
        }
        return ret;
    }



    //min  statck  维护两个栈，一个数据栈，一个村最小数据的栈
    private Stack<Integer> dataStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        dataStack.push(node);
        minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return minStack.peek();
    }

//数组中超过一半的数字
    public int MoreThanHalfNum_Solution(int[] nums) {
        int majority = nums[0];
        for (int i=1,cnt = 1; i < nums.length ; i++) {
            if(nums[i] == majority){
                cnt = cnt +1;
            }else {
                cnt = cnt -1;
            }
            if(cnt == 0) {
                majority = nums[i];
                cnt = 1;
            }
        }
        int cnt = 0;
        for (int num : nums) {
            if(num == majority) {
                cnt++;
            }
        }
        return cnt > nums.length/2  ? majority : 0;
    }

    //最小的k个数; PriorityQueue默认是小顶堆
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
        if (k > nums.length || k <= 0)
            return new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2) -> o2 -o1);//用大顶堆，维护最小堆
        for (int num : nums) {
            maxHeap.add(num);
            if(maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return new ArrayList<>(maxHeap);
    }


    // 数据流中的中位数，大顶堆中最大的数，小于等于小顶堆中最小的数，并且两个堆的数据个数不超过1
    PriorityQueue<Integer> left = new PriorityQueue<>((o1,o2) -> o2 -o1);//大顶堆，中存储
    PriorityQueue<Integer> right = new PriorityQueue<>();// 小丁对
    int N = 0;
    public void Insert(int val) {
        if(N%2 == 2) {//先插入右边
            left.add(val);
            right.add(left.poll());
        }else {
            right.add(val);
            left.add(right.poll());
        }
        N++;
    }

    public Integer getMidium() {
        if(N %2 == 0) {
            return (left.peek() +right.peek()  )/2 ;
        } else {
            return  right.peek();
        }
    }
}


